package LeetCode.LeetCode2;

/**
 * 丢失的数字
 * @author lumin
 * @date 2022/03/31 15:44
 **/
public class Num268 {
    public int missingNumber(int[] nums) {
        quickSort(nums);
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] - i == 1){
                return nums[i];
            }
        }
        return nums[nums.length - 1] + 1;
    }
    public static void quickSort(int[] nums){
        quickSortInternal(nums,0,nums.length - 1);
    }

    private static void quickSortInternal(int[] nums, int l, int r) {
        int p = partition(nums,l,r);
        quickSortInternal(nums,l,p - 1);
        quickSortInternal(nums,p,r);
    }

    private static int partition(int[] arr, int l, int r) {
        int v = arr[l];
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if(arr[i] < v){
                swap(arr,j + 1,i);
                j++;
            }
        }
        swap(arr,l,j);
        return j;
    }

    private static void swap(int[] arr, int l, int j) {
        int temp = arr[l];
        arr[l] = arr[j];
        arr[j] = temp;
    }
}